//
//  Problem1170.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/4/4.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1170. 比较字符串最小字母出现频次
 定义一个函数 f(s)，统计 s  中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。

 例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。

 现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。

 请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

 示例 1：
     输入：queries = ["cbd"], words = ["zaaaz"]
     输出：[1]
     解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
 示例 2：
     输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
     输出：[1,2]
     解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
 提示：
     1 <= queries.length <= 2000
     1 <= words.length <= 2000
     1 <= queries[i].length, words[i].length <= 10
     queries[i][j]、words[i][j] 都由小写英文字母组成
 */
@objcMembers class Problem1170: NSObject {
    func solution() {
        print(numSmallerByFrequency(["cbd"], ["zaaaz"]))
        print(numSmallerByFrequency(["bbb","cc"], ["a","aa","aaa","aaaa"]))
    }
    
    /*
     1: 首先求出words里面的每个单词的个数
     2: 在提示里面：每个单词的长度是 1～10，就是最小的单词量也永远是1～10，那么我们创建一个数组list，记录words中 最小为1的个数，最小为2的个数。。。最小为10的个数
     3: 然后倒叙求和，例如：list[10] = 0, 比10大的不存在，list[9] = list[10],  list[8] = list[9] + list[10]
     4: 遍历数组querires，求出每个字符串的最小单词数量 = n，那么他的个数就是list[n]
     */
    func numSmallerByFrequency(_ queries: [String], _ words: [String]) -> [Int] {

        var list:[Int] = Array(repeating: 0, count: 12)     //
        for word in words {
            var cc:Character = "{"
            var n = 0
            for c in word {
                if c == cc {
                    n += 1
                } else if c < cc {
                    n = 1
                    cc = c
                }
            }
            list[n] += 1
        }
        
//        print(list)
        var sum = 0
        var temp = 0
        for i in (0...10).reversed() {
            temp = list[i]
            list[i] = sum
            sum += temp
        }
        
//        print(list)
        
        var result:[Int] = []
        for querie in queries {
            var cc:Character = "{"
            var n = 0
            for c in querie {
                if c == cc {
                    n += 1
                } else if c < cc {
                    n = 1
                    cc = c
                }
            }
//            print(n)
            result.append(list[n])
        }
        
//        print(result)
        return result
    }
}
